Montgomery curve

In mathematics the Montgomery curve is a form of elliptic curve, different from the usual representation (Weierstrass form). It has been introduced by Peter L.Montgomery in,^[1] and it has been used since 1987 for certain computations, and in particular in different cryptography applications.

1 Definition
2 Montgomery arithmetic
3 Algorithm and example
- 3.1 Example
4 Addition
5 Doubling
6 Equivalence with twisted Edwards curves
7 Equivalence with Weierstrass curves
8 See also
9 Notes
10 References
11 External links

Definition

A Montgomery curve over a field $K$ is defined by the equation:

$M_{A,B}$ : $By^2 = x^3 %2B Ax^2 %2B x$

for certain $A,B \in K$ and with $B(A^2-4)\neq 0$ .

Generally this curve is considered over a finite field $K$ (for example over a finite field of q elements, $K=\mathbb{F}_q$ ) with characteristic different from 2 and with $A\in K\backslash\{-2,2\}$ , $B \in K\backslash\{0\}$ ; but they are also considered over the rationals with the same restrictions for A and B.

Montgomery arithmetic

It is possible to do some "operations" between the points of an elliptic curve: "adding" two points $P, Q$ consists on finding a third one $R$ such that $R=P%2BQ$ ; "doubling" a point consists on computing $[2]P=P%2BP$ (For more information about operations see The group law) and below.

A point $P=(x,y)$ on the elliptic curve in the Montgomery form $By^2 = x^3 %2B Ax^2 %2B x$ can be represented in Montgomery coordinates $P=(X:Z)$ , where $P=(X:Z)$ are projective coordinates and $x=X/Z$ for $Z\ne 0$ .

Notice that this kind of representation for a point loses information: indeed, in this case, there is no distinction between the affine points $(x,y)$ and $(x,-y)$ because they are both given by the point $(X:Z)$ . However, with this representation it is possible to obtain multiples of points, that is, given $P=(X:Z)$ , to compute $[n]P=(X_n:Z_n)$ .

Now, considering the two points $P_n=[n]P=(X_n:Z_n)$ and $P_m=[m]P(X_m:Z_m)$ : their sum is given by the point $P_{m%2Bn}=P_m%2BP_n = (X_{m%2Bn}:Z_{m%2Bn})$ whose coordinates are:

$X_{m%2Bn} = Z_{m-n}((X_m-Z_m)(X_n%2BZ_n)%2B(X_m%2BZ_m)(X_n-Z_n))^2$

$Z_{m%2Bn} = X_{m-n}((X_m-Z_m)(X_n%2BZ_n)-(X_m%2BZ_m)(X_n-Z_n))^2$

If $m=n$ , then the operation becomes a "doubling"; the coordinates of $[2]P_n=P_n%2BP_n=P_{2n}=(X_{2n}:Z_{2n})$ are given by the following equations:

$4X_nZ_n = (X_n%2BZ_n)^2 - (X_n-Z_n)^2$

$X_{2n} = (X_n%2BZ_n)^2(X_n-Z_n)^2$

$Z_{2n} = (4X_nZ_n)((X_n-Z_n)^2%2B((A%2B2)/4)(4X_nZ_n))$

The first operation considered above (addition) has a time-cost of 3M+2S, where M denotes the multiplication between two general elements of the field on which the elliptic curve is defined, while S denotes squaring of a general element of the field.

The second operation (doubling) has a time-cost of 2M+2S+1D, where D denotes the multiplication of a general element by a constant; notice that the constant is $(A%2B2)/4$ , so $A$ can be chosen in order to have a small D.

Algorithm and example

The following algorithm represents a doubling of a point $P_1=(X_1:Z_1)$ on an elliptic curve in the Montgomery form.

It is assumed that $Z_1=1$ . The cost of this implementation is 1M + 2S + 1*A + 3add + 1*4. Here M denotes the multiplications required, S indicates the squarings, and a refers to the multiplication by A.

$XX_1 = X_1^2 \,$

$X_3 = (XX_1-1)^2 \,$

$Z_3 = 4X_1(XX_1%2BaX_1%2B1) \,$

Example

Let $P_1=(2,\sqrt{3})$ be a point on the curve $2y^2 = x^3 -x^2 %2B x$ . In coordinates $(X_1:Z_1)$ , with $x_1=X_1/Z_1$ , $P_1=(2:1)$ .

Then:

$XX_1 = X_1^2 = 4 \,$

$X_3 = (XX_1-1)^2 = 9 \,$

$Z_3 = 4X_1(XX_1%2BaX_1%2B1) = 24 \,$

The result is the point $P_3=(X_3:Z_3)=(9:24)$ , such that $P_3=2P_1$ .

Addition

Given two points $P_1=(x_1,y_1)$ , $P_2=(x_2,y_2)$ on the Montgomery curve $M_{A,B}$ in affine coordinates, the point $P_3=P_1%2BP_2$ represents, geometrically the third point of intersection between $M_{A,B}$ and the line passing through $P_1$ and $P_2$ . It is possible to find the coordinates $(x_3,y_3)$ of $P_3$ , in the following way:

1) consider a generic line y=lx+m in the affine plane and let it pass through $P_1$ and $P_2$ (impose the condition), in this way, one obtains $l=\frac{y_2-y_1}{x_2-x_1}$ and $m=y_1-(\frac{y_2-y_1}{x_2-x_1})x_1$ ;

2) intersect the line with the curve $M_{A,B}$ , substituting the y variable in the curve equation with y=lx+m; the following equation of third degree is obtained:

$x^3%2B(A-Bl^2)x^2%2B(1-2Blm)x-m^2=0$ .

As it has been observed before, this equation has three solutions that correspond to the x coordinates of $P_1$ , $P_2$ and $P_3$ . In particular this equation can be re-written as:

$(x-x_1)(x-x_2)(x-x_3)=0$

3) Comparing the coefficients of the two identical equations given above, in particular the coefficients of the terms of second degree, one gets:

$-x_1-x_2-x_3=A-Bl^2$ .

So, $x_3$ can be written in terms of $x_1$ , $y_1$ , $x_2$ , $y_2$ , as:

$x_3 = B(\frac{y_2-y_1}{x_2-x_1})^2-A-x_1-x_2$ .

4) To find the y coordinate of the point $P_3$ it is sufficient to substitute the value $x_3$ in the line y=lx+m. Notice that this will not give the point $P_3$ directly. Indeed, with this method one find the coordinates of the point R such that $R%2BP_1%2BP_2=P_\infty$ , but if one needs the resulting point of the sum between $P_1$ and $P_2$ , then it is necessary to observe that: $R%2BP_1%2BP_2=P_\infty$ if and only if $-R=P_1%2BP_2$ . So, given the point R, it is necessary to find -R, but this can be done easily by changing the sign to the y coordinate of R. In other words, it will be necessary to change the sign of the y coordinate obtained by substituting the value $x_3$ in the equation of the line.

Resuming, the coordinates of the point $P_3=(x_3,y_3)$ , $P_3=P_1%2BP_2$ are:

$x_3 = \frac{B(y_2-y_1)^2}{(x_2-x_1)^2}-A-x_1-x_2$

$y_3 = \frac{(2x_1%2Bx_2%2BA)(y_2-y_1)}{x_2-x_1}-\frac{B(y_2-y_1)^3}{(x_2-x_1)^3}-y_1$

Doubling

Given a point $P_1$ on the Montgomery curve $M_{A,B}$ , the point $[2]P_1$ represents geometrically the third point of intersection between the curve and the line tangent to $P_1$ ; so, to find the coordinates of the point $P_3=2P_1$ it is sufficient to follow the same method given in the addition formula; however, in this case, the line y=lx+m has to be tangent to the curve at $P_1$ , so, if $M_{A,B}: f(x,y)=0$ with

$f(x,y)=x^3%2BAx^2%2Bx-By^2$ ,

then the value of l, which represents the slope of the line, is given by:

$l=-\frac{\frac{\partial f}{\partial x}}{\frac{\partial f}{\partial y }}$

by the implicit function theorem.

So $l = \frac{3x_1^2 %2B 2Ax_1 %2B 1}{2By_1}$ and the coordinates of the point $P_3$ , $P_3=2P_1$ are:

$x_3 = Bl^2-A-x_1-x_1 = \frac{B(3x_1^2%2B2Ax_1%2B1)^2}{(2By_1)^2}-A-x_1-x_1$

$y_3 = (2x_1%2Bx_1%2BA)l-Bl^3-y_1 = \frac{(2x_1%2Bx_1%2BA)(3{x_1}^2%2B2Ax_1%2B1)}{(2By_1)}-\frac{B(3{x_1}^2%2B2Ax_1%2B1)^3}{(2By_1)^3}-y_1$ .

Equivalence with twisted Edwards curves

Let $K$ be a field with characteristic different from 2.

Let $M_{A,B}$ be an elliptic curve in the Montgomery form:

$M_{A,B}$ : $Bv^2 = u^3 %2B Au^2 %2B u$

with $A\in K\backslash\{-2,2\}$ , $B \in K\backslash\{0\}$

and let $E_{a,d}$ be an elliptic curve in the twisted Edwards form:

$E_{a,d}\ �:\ ax^2 %2B y^2 = 1 %2B dx^2y^2, \,$

with $a,d\in K\backslash\{0\}$ , $a\neq d$ .

The following theorem proved in,^[2] shows the birational equivalence between Montgomery curves and an twisted Edwards curves:

Theorem (i) Every twisted Edwards curve is birationally equivalent to a Montgomery curve over $K$ . In particular, the twisted Edwards curve $E_{a,d}$ is birationally equivalent to the Montgomery curve $M_{A,B}$ where $A = \frac{2(a%2Bd)}{a-d}$ , and $B = \frac{4}{a-d}$ .

The map:

$\psi\,:\,E_{a,d} \rightarrow M_{A,B}$

$(x,y) \mapsto (u,v) = \left(\frac{1%2By}{1-y},\frac{1%2By}{(1-y)x}\right)$

is a birational equivalence from $E_{a,d}$ to $M_{A,B}$ , with inverse:

$\psi^{-1}$ : $M_{A,B} \rightarrow E_{a,d}$

$(u,v) \mapsto (x,y) = \left(\frac{u}{v},\frac{u-1}{u%2B1}\right)$

Notice that this equivalence between the two curves is not valid everywhere: indeed the map $\psi$ is not defined at the points $v = 0$ or $u %2B 1 = 0$ of the $M_{A,B}$ .

Equivalence with Weierstrass curves

Any elliptic curve can be written in Weierstrass form.

So, the elliptic curve in the Montogmery form

$M_{A,B}$ : $By^2 = x^3 %2B Ax^2 %2B x$ ,

can be transformed in the following way: divide each term of the equation for $M_{A,B}$ by $B^3$ , and substitute the variables x and y, with $u=\frac{x}{B}$ and $v=\frac{y}{B}$ respectively, to get the equation

$v^2 = u^3 %2B \frac{A}{B}u^2 %2B \frac{1}{B^2}u$ .

To obtain a short Weierstrass form from here, it is sufficient to replace u with the variable $t-\frac{A}{3B}$ :

$v^2 = \left(t-\frac{A}{3B}\right)^3 %2B \frac{A}{B}\left(t-\frac{A}{3B}\right)^2 %2B \frac{1}{B^2}\left(t-\frac{A}{3B}\right)$ ;

finally, this gives the equation:

$v^2 = t^3 %2B \left(\frac{3-A^2}{3B^2}\right)t %2B \left(\frac{2A^3-9A}{27B^3}\right)$ .

Notes

^ Peter L. Montgomery, Speeding the Pollard and Elliptic Curve Methods of Factorization, January 1987
^ Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange and Christiane Peters, Twisted Edwards Curves

References

Peter L. Montgomery (1987). Speeding the Pollard and Elliptic Curve Methods of Factorization. American Mathematical Society. JSTOR 2007888.
Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange and Christiane Peters (2008). Twisted Edwards Curves. Springer-Verlag Berlin Heidelberg. ISBN 978-3-540-68159-5. http://www.springerlink.com.proxy.library.uu.nl/content/m37m171510425501/fulltext.pdf.
Wouter Castryck, Steven Galbraith, Reza Rezaeian Farashahi. Efficient Arithmetic on Elliptic Curves using a Mixed Edwards-Montgomery Representation. http://wis.kuleuven.be/algebra/castryck/xcoordinate.pdf.

External links

Genus-1 curves over large-characteristic fields